package base.variable;

public class StageMain {
	private static int stage = 40;//剩余台阶
    private static final int staticStage = 40;//总台阶
    private static int sum = 0;//完成的可能性数(多少种走法)

	public static void main(String[] args) {
		System.out.println(System.currentTimeMillis());
		int i = f(40);
		System.out.println(i);
		System.out.println(System.currentTimeMillis());
		i = f2(40);
		System.out.println(i);
		System.out.println(System.currentTimeMillis());
		i = goStage(0, 0);
		System.out.println(System.currentTimeMillis());
		System.out.println(i);
	}
	
	/**
	 * @param n
	 * @return
	 * G_Y
	 * 2018年3月15日
	 * 说明:(走到 n层台阶的 总方法数) = (走到n-1层台阶的 总方式数) + (走到n-2 层台阶的 总方式数)  然后 直接 一个 方法 出来答案了
	 * f(n) = f(n-1) + f(n-2);
	 */
	public static int f(int n){
	    if(n <= 2) return n;
	    int x = f(n-1) + f(n-2);
	    return x;
	}
	
	public static int f2(int n) {  
	    if (n <= 2){  
	        return n;  
	    }  
	   
	    int first = 1, second = 2;
	    int third = 0;
	    for (int i = 3; i <= n; i++) {
	        third = first + second;
	        first = second;
	        second = third;
	    }  
	    return third;  
	}  

	private static int goStage(int one, int two){
        if(one!=0 || two!=0){
            //计算剩余层数
            stage = staticStage-one-two*2;
        }
        if(stage<1){
            //走到最后是方式加一
            sum++;
            return sum;
            //System.out.println(sum);
        }
        if(stage>1){
            //剩余一曾以上,下一步可跨1层、可跨2层
            for(int i=1;i<=2;i++){
                if(i==1){
                    goStage(one+1, two);
                }
                if(i==2){
                    goStage(one, two+1);
                }
            }
        }
        if(stage == 1){
            //剩余一曾,下一步只能选择走一曾
            goStage(one+1,two);
        }
        return sum;
    }
	
}
